package kibahed.university.effizientealgorithmen.algortihms;

import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

import kibahed.university.effizientealgorithmen.interfaces.AAlgorithm;
import kibahed.university.effizientealgorithmen.interfaces.IEdge;
import kibahed.university.effizientealgorithmen.interfaces.IGraph;
import kibahed.university.effizientealgorithmen.standardclasses.EdgeWithCosts;
@Deprecated
public class showAdditionalLinesExtendedSimpleMatching extends AAlgorithm {

	PriorityQueue<EdgeWithCosts> queue = new PriorityQueue<EdgeWithCosts>();

	PriorityQueue<EdgeWithCosts> oddEdges = new PriorityQueue<EdgeWithCosts>();

	Set<IEdge> minimalSpanningTree = new HashSet<IEdge>();

	int[] parts = null;
	int[] sz = null;
	int[] connectionCount = null;
	Set<Integer> oddNodes = new HashSet<Integer>();

	@SuppressWarnings("unchecked")
	public showAdditionalLinesExtendedSimpleMatching(IGraph graph) {
		setGraph(graph);
		queue.addAll((Collection<? extends EdgeWithCosts>) graph.getEdges());
		parts = new int[graph.getVertexes().length];
		connectionCount = new int[graph.getVertexes().length];
		initParts();
		sz = new int[graph.getVertexes().length];
	}

	private void initParts() {
		for (int i = 0; i < parts.length; i++) {
			parts[i] = i;
		}
	}

	private void updateParts(int start, int end) {
		int newEnd = parts[end];
		for (int i = 0; i < parts.length; i++) {
			if (parts[i] == newEnd) {
				parts[i] = parts[start];
			}
		}
	}

	@Override
	public void calculate() {
		System.out.println("STARTING KRUSKAL");
		do {
			IEdge e = queue.remove();
			int start = e.getStart();
			int end = e.getEnd();
			if ((parts[start] != parts[end])) {
				minimalSpanningTree.add(e);
				connectionCount[start]++;
				connectionCount[end]++;
				System.out.println(connectionCount[start]);
				updateParts(start, end);

			}

		} while (!queue.isEmpty());

		double length = 0;
		for (IEdge e : minimalSpanningTree) {
			length += ((EdgeWithCosts) e).getCost();
		}

		System.out.println("Length of minimal spanning tree = " + length);

		graph.setEdgeTour(minimalSpanningTree
				.toArray(new IEdge[minimalSpanningTree.size()]));

		for (int node = 0; node < graph.getVertexes().length; node++) { // All
																		// odd
																		// nodes
			if (connectionCount[node] % 2 == 1) {
				oddNodes.add(node);
			}
		}

		for (int node : oddNodes) {
			for (IEdge edge : graph.getVertexes()[node].getEdges()) {
				if (oddNodes.contains(edge.getStart())
						&& oddNodes.contains(edge.getEnd())&&!minimalSpanningTree.contains(edge)) {
					oddEdges.add((EdgeWithCosts) edge);
				}
			}
		}

		List<IEdge> newEdges = new LinkedList<IEdge>();
		do {
			EdgeWithCosts edge = oddEdges.remove();
			if (oddNodes.contains(edge.getStart())
					&& oddNodes.contains(edge.getEnd())) {
				oddNodes.remove(edge.getStart());
				oddNodes.remove(edge.getEnd());
				newEdges.add(edge);
			}
		} while (!oddEdges.isEmpty());
		minimalSpanningTree.addAll(newEdges);
		connectionCount = new int[graph.getVertexes().length];
		for (IEdge e : minimalSpanningTree) {
			connectionCount[e.getStart()]++;
			connectionCount[e.getEnd()]++;
		}
		int currentNode = 0;
//		do {
//
//			int count = 0;
//			PriorityQueue<EdgeWithCosts> unbalancedEdges = new PriorityQueue<EdgeWithCosts>();
//			for (IEdge e : minimalSpanningTree) {
//				if (e.getStart() == currentNode || e.getEnd() == currentNode) {
//					unbalancedEdges.add((EdgeWithCosts) e);
//					
//					count++;
//				}
//			}
//			if (count == 3) {
//				int count1=0, count2=0, count3=0;
//				EdgeWithCosts edge1 = unbalancedEdges.remove();
//				EdgeWithCosts edge2 = unbalancedEdges.remove();
//				EdgeWithCosts edge3 = unbalancedEdges.remove();
//				int pos1 = 0;
//				if (edge1.getStart() == currentNode) {
//					pos1 = edge1.getEnd();
//				} else {
//					pos1 = edge1.getStart();
//				}
//				int pos2 = 0;
//				if (edge2.getStart() == currentNode) {
//					pos2 = edge2.getEnd();
//				} else {
//					pos2 = edge2.getStart();
//				}
//				int pos3 = 0;
//				if (edge3.getStart() == currentNode) {
//					pos3 = edge3.getEnd();
//				} else {
//					pos3 = edge3.getStart();
//				}
//				
//				for (IEdge edge :minimalSpanningTree) {
//					if ((edge.getStart() == pos1&&edge.getEnd()==currentNode)||(edge.getEnd() == pos1&&edge.getStart()==currentNode)){
//						count1++;
//					}
//					if ((edge.getStart() == pos2&&edge.getEnd()==currentNode)||(edge.getEnd() == pos2&&edge.getStart()==currentNode)){
//						count2++;
//					}
//					if ((edge.getStart() == pos3&&edge.getEnd()==currentNode)||(edge.getEnd() == pos3&&edge.getStart()==currentNode)){
//						count3++;
//					}
//				}
//				if(count1==1){
//					minimalSpanningTree.add(getEdge(pos1,pos2));
//					minimalSpanningTree.remove(getEdge(pos2,currentNode));
//				}else if(count2==1){
//					minimalSpanningTree.add(getEdge(pos2,pos3));
//					minimalSpanningTree.remove(getEdge(pos3,currentNode));
//				}else if(count3==1){
//					minimalSpanningTree.add(getEdge(pos3,pos1));
//					minimalSpanningTree.remove(getEdge(pos1,currentNode));
//				}
//				continue;
//			}
//
//			if (count == 4) {
//				unbalancedEdges.remove();
//				EdgeWithCosts remainingEdge = unbalancedEdges.remove();
//				EdgeWithCosts edge1 = unbalancedEdges.remove();
//				EdgeWithCosts edge2 = unbalancedEdges.remove();
//				if(edge1.getStart()==edge2.getEnd()&&edge1.getEnd()==edge2.getStart()){
//					edge1=remainingEdge;
//				}
//				int pos1 = 0;
//				if (edge1.getStart() == currentNode) {
//					pos1 = edge1.getEnd();
//				} else {
//					pos1 = edge1.getStart();
//				}
//				int pos2 = 0;
//				if (edge2.getStart() == currentNode) {
//					pos2 = edge2.getEnd();
//				} else {
//					pos2 = edge2.getStart();
//				}
//				for (IEdge edge : graph.getEdges()) {
//					if ((edge.getStart() == pos1 && edge.getEnd() == pos2)
//							|| (edge.getStart() == pos2 && edge.getEnd() == pos1)) {
//						minimalSpanningTree.add(edge);
//
//						minimalSpanningTree.remove(edge1);
//						minimalSpanningTree.remove(edge2);
//
//						break;
//					}
//				}
//				currentNode = 0;
//			} else {
//				currentNode++;
//			}
//
//		} while (currentNode != graph.getVertexes().length);

		graph.setEdgeTour(newEdges
				.toArray(new IEdge[newEdges.size()]));
		setResult(newEdges
				.toArray(new IEdge[newEdges.size()]));
	}

	private IEdge getEdge(int pos1, int pos2) {
		for(IEdge edge:graph.getEdges()){
			if((edge.getStart()==pos1&&edge.getEnd()==pos2)||(edge.getStart()==pos2&&edge.getEnd()==pos1)){
				return edge;
			}
		}
		return null;
	}
}
